//
//  113. 路径总和.swift
//  Top600
//
//  Created by rjb on 2021/7/28.
//

import Foundation

class Solution113 {
    // 采用深度优先遍历即可
    var path: [Int] = []
    var sum: Int = 0
    var result: [[Int]] = []
    func pathSum(_ root: TreeNode?, _ targetSum: Int) -> [[Int]] {
       preOrder(root, targetSum)
        return result
    }
    func preOrder(_ node: TreeNode?, _ targetSum: Int) {
        guard let node = node else {
            return
        }
        // 加入路径
        sum += node.val
        // 路径
        path.append(node.val)
        if sum == targetSum && node.left == nil && node.right == nil {
            result.append(path)
        }
        preOrder(node.left, targetSum)
        preOrder(node.right, targetSum)
        // 移除路径
        sum -= node.val
        path.removeLast()
    }
    static func test() {
        let solution = Solution113()
        
        let node5 = TreeNode(5)
        let node4 = TreeNode(4)
        let node11 = TreeNode(11)
        let node7 = TreeNode(7)
        let node2 = TreeNode(2)
        let node8 = TreeNode(8)
        let node13 = TreeNode(13)
        let node44 = TreeNode(4)
        let node55 = TreeNode(5)
        let node1 = TreeNode(1)
        
        node5.left = node4
        node4.left = node11
        node11.left = node7
        node11.right = node2
        node5.right = node8
        node8.left = node13
        node8.right = node44
        node44.left = node55
        node44.right = node1
        
        let targetSum = 22
        let result = solution.pathSum(node5, targetSum)
        print(result)
    }
}
